#include <iostream>

template<typename T> class List;

template<typename T> class Node{
	
	T info;
	Node<T> *link;

public:
	Node();
	Node(const T & data);
	Node<T> * RemoveAfter();
	T get_info();
	void set_info(double x);
 	friend class List <T>;
};

template <typename T> Node<T>::Node(){link = NULL ;}

template <typename T> Node<T>::Node(const T & data){
	info = data;
	link = NULL;
}

template <typename T> Node<T> * Node<T>::RemoveAfter(){
	Node<T> * tempP = link;
	if (link == NULL) tempP = NULL;
	else link = tempP ->link;
	return tempP;
}

template <typename T> T Node<T>:: get_info(){
	return info;
}

template <typename T> void Node<T>::set_info(double x){
     info.set_h(x);

}

// ************
//  list
//*************

template <typename T> class List{
	Node<T> * head , *tail;
public:
	List();
	~List();
	void MakeEmpty();
	bool isEmpty();
	Node<T> * Find(int x, int y);
	void PrintList();
	void InsertFront(Node<T> * p);
	void InsertRear(Node<T> * p);
	void InsertOrder(Node<T> * p);
	Node<T> * CreatNode(T data);
	Node<T> * DeleteNode(Node<T> *p);
	Node<T> * DeleteRear();
	Node<T> * DeleteFront();
};

template<typename T> List<T> ::List(){
	head = tail = new Node<T>();
}

template<typename T> List <T>:: ~List(){
	MakeEmpty();
//	delete head;
}

template <typename T> void List<T> ::MakeEmpty(){
	//Node<T> * tempP;
	//while(head->link != NULL){
	//	tempP = head->link;
	//	delete tempP;
//	delete head;
}

template <typename T> bool List<T> ::isEmpty(){
	return tail == head;
}

template <typename T> Node<T> * List<T>::Find(int x , int y){
	Node<T> * tempP = head->link;
	while(tempP!=NULL && ( tempP -> info.get_x() != x || tempP -> info.get_y() != y) )  tempP = tempP->link;
	return tempP;
}

template <typename T> void List<T> :: PrintList(){
	Node<T> * tempP = head->link;
	while(tempP != NULL){
		printf("(%1.0f ,%5.0f, %2.1d, %2.1d)\n" , tempP->info.get_i() , 
			tempP->info.get_h() , tempP->info.get_x() , tempP->info.get_y());
		tempP = tempP -> link;
	}
}

template <typename T> void List<T> :: InsertFront(Node<T> * p){
	p -> link = head ->link;
	head -> link = p;
	if(tail == head) tail = p;
}

template <typename T> void List<T> :: InsertRear(Node<T> * p){
	p -> link = tail ->link ; 
	tail -> link = p;
	tail = p;
}

template <typename T> void List<T> :: InsertOrder(Node<T> * p) {
	Node<T> * tempP = head->link , *tempQ = head;
	while(tempP != NULL){
		if (p->info.get_h() < tempP-> info.get_h()) break;  // >=

		tempQ = tempP;

		tempP = tempP->link;
	}

//tempQ -> InsertAfter(p);

	p->link = tempQ->link; 
    tempQ->link = p;
	
   if(tail == tempQ) tail = tempQ -> link;
}

template<typename T> Node<T> * List<T> :: CreatNode(T data){
	Node<T> * tempP = new Node<T> (data);
	return tempP;
}

template<typename T> Node<T> * List<T> :: DeleteNode(Node <T> * p){
	Node<T> * tempP = head;

	while(tempP ->link!=NULL && tempP->link!=p) tempP = tempP ->link;
	if(tempP->link == tail) tail = tempP;
	return tempP-> RemoveAfter();
}

template<typename T> Node<T> * List<T> :: DeleteRear(){
	
	Node<T> * tempP = head;

	while(tempP ->link!=tail) tempP = tempP ->link;
	tail = tempP;
	return tempP-> RemoveAfter();
}

template<typename T> Node<T> * List<T> :: DeleteFront(){
	
	Node<T> * tempP = head->link;

	if (tempP == tail) {
		head = tail;
	}
	else head->link = tempP->link;

	return tempP;
}

